#[derive(Debug)]
pub struct Queue<T> {
	qdata: Vec<T>,
}

impl <T> Queue<T> {
	pub fn new() -> Self {
		Queue{qdata: Vec::new()}
	}

	pub fn push(&mut self, item:T) {
		self.qdata.push(item);
	}

	pub fn pop(&mut self) -> Option<T>{
		if self.qdata.len() > 0 {
			Some(self.qdata.remove(0))
		} else {
			None
		}
	}
}


// priority queue
#[derive(Debug)]
pub struct PriorityQueue<T> where T: PartialOrd + Clone {
	pq: Vec<T>,
}

impl <T> PriorityQueue<T> where T: PartialOrd + Clone {
	pub fn new() -> PriorityQueue<T> {
		PriorityQueue{ pq: Vec::new()}
	}

	pub fn len(&self) -> usize {
		self.pq.len()
	}

	pub fn is_empty(&self) -> bool {
		self.len() == 0
	}

	pub fn insert(&mut self, value:T) {
		self.pq.push(value);
	}

	pub fn max(&self) -> Option<T> {
		if self.is_empty() { return None}
		let max = self.max_index();
		Some(self.pq[max].clone())
	}

	pub fn min(&self) -> Option<T> {
		if self.is_empty() { return None}
		let min = self.min_index();
		Some(self.pq[min].clone())
	}

	pub fn delete_max(&mut self) -> Option<T>{
		if self.is_empty() { return None }
		let max = self.max_index();
		Some(self.pq.remove(max).clone())
	}

	pub fn delete_min(&mut self) -> Option<T> {
		if self.is_empty() { return None }
		let min = self.min_index();
		Some(self.pq.remove(min).clone())
	}

	pub fn max_index(&self) -> usize {
		let mut max = 0;
		for i in 1 .. self.pq.len() {
			if self.pq[max] < self.pq[i] {
				max = i;
			}
		}
		max
	}

	pub fn min_index(&self) -> usize {
		let mut min = 0;
		for i in 0..self.pq.len(){
			if self.pq[min] > self.pq[i] {
				min = i;
			}
		}
		min
	}
}


#[cfg(test)]
mod tests {
	use super::*;
    #[test]
    fn queue_test() {
        let mut q = Queue::new();
        q.push(1);
        q.push(2);

        assert_eq!(1, q.pop().unwrap());
        assert_eq!(2, q.pop().unwrap());
    }

    #[test]
    fn pq_test() {
    	let mut pq = PriorityQueue::new();
    	assert!(pq.is_empty());

    	pq.insert(3);
    	pq.insert(2);

    	assert!(!pq.is_empty());

    	assert_eq!(pq.len(), 2);

    	pq.insert(1);
    	pq.insert(4);
    	assert_eq!(pq.min().unwrap(), 1);
    	assert_eq!(pq.max().unwrap(), 4);

    	assert_eq!(pq.delete_max().unwrap(), 4);
    	assert_eq!(pq.delete_min().unwrap(), 1);
    }
}
